package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例 - x 的平方根
        Solution solution1 = new Solution();
        System.out.println("x 的平方根:");
        System.out.println("sqrt(4) = " + solution1.mySqrt(4)); // 2
        System.out.println("sqrt(8) = " + solution1.mySqrt(8)); // 2
        System.out.println("sqrt(0) = " + solution1.mySqrt(0)); // 0
        System.out.println("sqrt(1) = " + solution1.mySqrt(1)); // 1

        // 测试用例 - 搜索插入位置
        Solution2 solution2 = new Solution2();
        System.out.println("\n搜索插入位置:");
        int[] nums1 = {1, 3, 5, 6};
        System.out.println("nums=[1,3,5,6], target=5: " + solution2.searchInsert(nums1, 5)); // 2
        System.out.println("nums=[1,3,5,6], target=2: " + solution2.searchInsert(nums1, 2)); // 1
        System.out.println("nums=[1,3,5,6], target=7: " + solution2.searchInsert(nums1, 7)); // 4
        System.out.println("nums=[1,3,5,6], target=0: " + solution2.searchInsert(nums1, 0)); // 0
    }

    // x 的平方根
    static class Solution {
        public int mySqrt(int x) {
            if (x < 1) {
                return 0;
            }
            long left = 0, right = x;
            while (left < right) {
                long mid = left + (right - left + 1) / 2;
                if (mid * mid <= x) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            return (int) left;
        }
    }

    // 搜索插入位置
    static class Solution2 {
        public int searchInsert(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] >= target) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            if (nums[left] < target) {
                return left + 1;
            }
            return left;
        }
    }
}